﻿//
// Created by Freeman on 2022/3/8.
//

/**
 * 算法初步
 */

#ifndef PAT_EXERCISES_PRELIMINARY_ALGORITHM_H
#define PAT_EXERCISES_PRELIMINARY_ALGORITHM_H

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

class PAT_A1070 {
    class MoonCake {
        friend class PAT_A1070;

    private:
        double storage, totalValue = 0;
        double unitPrice = 0; // 单价

    public:
        MoonCake(double storage, double totalValue) : storage(storage), totalValue(totalValue) {
            unitPrice = totalValue / storage;
        }

        explicit MoonCake(double storage) : storage(storage) {
        }

        void setTotalValue(double value) {
            this->totalValue = value;
            unitPrice = value / storage;
        }

        static bool comp(const MoonCake &objA, const MoonCake &objB) {
            return objA.unitPrice > objB.unitPrice;
        }
    };

public:
    static void solve() {
        int nTypes;
        double demand;
        std::cin >> nTypes >> demand;
        std::vector<MoonCake> moonCakeTypes;
        for (int i = 1; i <= nTypes; i++) {
            double storage;
            std::cin >> storage;
            moonCakeTypes.emplace_back(storage);
        }
        for (int i = 1; i <= nTypes; i++) {
            double totalValue;
            std::cin >> totalValue;
            moonCakeTypes[i - 1].setTotalValue(totalValue);
        }
        std::sort(moonCakeTypes.begin(), moonCakeTypes.end(), MoonCake::comp); // 按单价从大到小排序
        double profit = 0;
        for (int i = 0; i < nTypes; i++) {
            if (demand >= moonCakeTypes[i].storage) {
                demand -= moonCakeTypes[i].storage;
                profit += moonCakeTypes[i].totalValue;
            }
            else {
                profit += demand * moonCakeTypes[i].unitPrice;
                break; // 当前种类月饼能满足全部需求，终止循环
            }
        }
        std::cout << setiosflags(std::ios::fixed) << std::setprecision(2) << profit;
    }
};

/**
 * 区间选择问题的贪心解法。假设活动占用的时间区间均为开区间。
 */
class IntervalSelection {
    class Activity {
        friend class IntervalSelection;

    private:
        int begin, end;

    public:
        Activity(int begin, int end) : begin(begin), end(end) {}

        /**
         * 依据开始时间排序，开始时间较早的排在前面。
         */
        static bool sortByBegin(const Activity &actA, const Activity &actB) {
            return actA.begin < actB.begin;
        }

        /**
         * 根据结束时间排序，结束时间较早的排在后面。
         */
        static bool sortByEnd(const Activity &actA, const Activity &actB) {
            return actA.end < actB.end;
        }
    };

public:
    /**
     * 解函数
     * @param acts 活动向量。假设不存在覆盖其他活动的活动。
     */
    static std::vector<Activity> solve(std::vector<Activity> acts) {
        std::vector<Activity> chosen;
        if (acts.empty()) return chosen;

        std::sort(acts.begin(), acts.end(), Activity::sortByEnd);
        chosen.push_back(*acts.begin()); // 选择最早结束的活动
        acts.erase(acts.begin());
        while (!acts.empty() && acts[0].end > chosen[0].begin) acts.erase(acts.begin()); // 去除重叠活动
        std::vector<Activity> subSolution = solve(acts);
        chosen.insert(chosen.end(), subSolution.begin(), subSolution.end()); // 拼接子问题的解
        return chosen;
    }
};

// ============================== 参考过题解的问题 ==============================

/**
 * 贪心策略：将汽车载满油时能行驶的距离称为“覆盖范围”。
 * 对于每一个站点，如果覆盖范围内有更便宜的站点，则加到刚好能到此站点。
 * 否则：如果终点已在范围内，则加到刚好能到终点；否则加满，并前往覆盖范围内尽可能便宜的站点。
 */
class PAT_A1033 {
    class Station {
        friend class PAT_A1033;

    private:
        double unitPrice;
        double srcDist; // 距起点的距离

    public:
        Station(double unitPrice, double srcDist) : unitPrice(unitPrice), srcDist(srcDist) {}

        static bool sortByDist(const Station &objA, const Station &objB) {
            return objA.srcDist < objB.srcDist;
        }
    };

private:
    double maxCapacity, totalDist, distPerUnitGas;
    double fullTankTravelDist; // 油箱加满时可以前进多少距离
    int nStations;
    std::vector<Station> stations;

public:
    PAT_A1033() {
        std::cin >> maxCapacity >> totalDist >> distPerUnitGas >> nStations;
        fullTankTravelDist = maxCapacity * distPerUnitGas;
        for (int i = 0; i < nStations; i++) {
            double unitPrice, dist;
            std::cin >> unitPrice >> dist;
            stations.emplace_back(unitPrice, dist);
        }
    }

    void solve() {
        std::sort(stations.begin(), stations.end(), Station::sortByDist);
        double maxTravelDist = calcMaxTravelDist();
        cout << std::setiosflags(std::ios::fixed) << std::setprecision(2);
        if (maxTravelDist < totalDist) { // 无法到达终点
            cout << "The maximum travel distance = " << maxTravelDist;
            return;
        }

        int curIdx = 0;
        double travelDist = 0; // 当前油量能前进多远
        double totalPrice = 0;
        while (true) {
            Station &curStation = stations[curIdx];
            double addedDist; // 增加的行驶距离
            int cheaperIdx = findCheaper(curIdx);
            if (cheaperIdx == -1) { // 覆盖范围内不存在更便宜的加油站
                if (curStation.srcDist + fullTankTravelDist > totalDist) { // 终点在范围内
                    addedDist = totalDist - curStation.srcDist - travelDist;
                    totalPrice += addedDist / distPerUnitGas * curStation.unitPrice;
                    break;
                }

                else { // 否则加满
                    addedDist = fullTankTravelDist - travelDist;
                    travelDist = fullTankTravelDist;
                    totalPrice += addedDist / distPerUnitGas * curStation.unitPrice;

                    int nextIdx = findNextStation(curIdx); // 下一个加油的加油站
                    Station &nextStation = stations[nextIdx];
                    curIdx = nextIdx;
                    travelDist -= (nextStation.srcDist - curStation.srcDist);
                }
            }
            else { // 存在更便宜的加油站，加到刚好能到此加油站
                Station &cheaperStation = stations[cheaperIdx];
                addedDist = cheaperStation.srcDist - curStation.srcDist - travelDist;
                totalPrice += addedDist / distPerUnitGas * curStation.unitPrice;

                curIdx = cheaperIdx;
                travelDist = 0;
            }
        }

        cout << totalPrice;
    }

private:
    /**
     * 计算最远能到达的位置。
     */
    double calcMaxTravelDist() {
        if (stations[0].srcDist > 0) return 0; // 特殊情况：最近的加油站距离不为0

        for (int i = 0; i < stations.size() - 1; i++) {
            if (stations[i + 1].srcDist - stations[i].srcDist > fullTankTravelDist) { // 无法到达第i+1个站点
                return stations[i].srcDist + fullTankTravelDist;
            }
        }
        return stations[stations.size() - 1].srcDist + fullTankTravelDist; // 最远距离为最后一个站点+满载前进距离
    }

    /**
     * 寻找第idx个站点覆盖范围内第一个单价更便宜的站点，返回其下标。如果覆盖范围内不存在这样的站点，返回-1.
     */
    int findCheaper(int curIdx) {
        Station &curStation = stations[curIdx];
        for (int i = curIdx + 1; i < stations.size(); i++) {
            Station &station = stations[i];
            if (station.srcDist - curStation.srcDist > fullTankTravelDist) { // 考察的站点在本站点的覆盖范围之外
                return -1;
            }
            if (station.unitPrice < curStation.unitPrice) return i;
        }
        return -1; // 到达列表尾
    }

    /**
     * 在不存在更便宜站点的情况下，找出尽可能便宜的站点。函数默认终点不在当前站点覆盖范围内。
     */
    int findNextStation(int curIdx) {
        Station &curStation = stations[curIdx];
        double cheapestUnitPrice = stations[curIdx + 1].unitPrice;
        int nextIdx = curIdx + 1;
        int i = curIdx + 2;
        for (; i < nStations; i++) {
            if (stations[i].srcDist - curStation.srcDist > fullTankTravelDist) break;
            if (stations[i].unitPrice < cheapestUnitPrice) {
                cheapestUnitPrice = stations[i].unitPrice;
                nextIdx = i;
            }
        }
        return nextIdx;
    }
};

#endif //PAT_EXERCISES_PRELIMINARY_ALGORITHM_H
